"""矿工挖矿问题是为了解决在给定金矿和矿工数量的前提下，能够获得最多黄金的挖矿策略。

某一地区发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。
假设参与挖矿工人的总数是 10 人，且每座金矿要么全挖，要么不挖，
不能派出一半人挖取一半金矿。
要求用程序求解，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

金矿的黄金储量与所需挖掘工人的数量如表所示。


    金矿编号    黄金储量    所需工人数量
      1          400         5
      2          500         5
      3          200         3
      4          300         4
      5          350         3
"""


def goldMine(n, m, G, L):
    """
    定义一个动态规划函数
    :param n: 矿产数量
    :param m: 矿工数
    :param G: 矿产列表
    :param L: 矿工列表
    :return:
    """
    # 首先初始化一个结果列表，用来保存只选择第一个矿产时的情况
    t_results = [0 for i in range(m + 1)]

    # 循环遍历矿工人数，从1个人一直增加到m个人
    for i in range(1, m + 1):
        # L[0]表示挖第一个矿需要的矿工人数
        if i < L[0]:  # 当前的矿工人数不足挖第一个矿
            t_results[i] = 0  # 当前得到的矿为0个
        else:
            t_results[i] = G[0]  # 当前得到的矿为第一个矿的矿数

    # 循环挖剩下的矿产
    for i in range(1, n):
        # 初始化结果列表
        results = [0 for i in range(m + 1)]

        # 循环遍历矿工人数，从1个人一直增加到m个人
        for j in range(1, m + 1):
            if j < L[i]:  # L[i]表示挖当前（第i+1个）矿产需要的人数
                results[j] = t_results[j]  # 如果当前人数不够挖当前矿产的，则当前矿工得到的矿产为上一层的情况
            else:  # 如果当前人数可以挖当前的矿产，则需要进行比较（挖当前矿产和不挖哪个获得的矿产多）
                # 这一行代码不是很好理解，我们可以慢慢解读，举个例子来说更具体一点
                # 例如：假设我们当前有8个人，而当前我们在第2个矿产处，我们知道挖第2个矿产需要5个人
                # 很明显此时我们可以挖当前矿产，这时候我们需要在挖与不挖中做个选择
                # t_results[j]表示不挖，那么我们直接取上一层的结果即可
                # t_results[j-L[i]]+G[i]表示挖，那么我们将取上一层中的t_results[3]和挖第2个矿得到的矿数总数
                # t_results[3]表示上一层3个矿工可以得到的矿数（因为挖本层需要用掉5个矿工，所以只剩3个矿工了）
                results[j] = max(t_results[j], t_results[j - L[i]] + G[i])
        t_results = results  # 更新当前的结果列表作为下一层的上层结果
    return results[-1]


# 结果有点不对
def goldMining(n, w, g, p):
    results = []  # 保存返回结果的数组
    preResults = []  # 保存上一行结果的数组
    for i in range(0, w):  # 填充边界格子的值，从左向右填充表格第一行的内容
        results.append(0)  # 初始化结果数组
        if i < p[0]:
            preResults.append(0)  # 若人数少于第一座金矿所需人数，黄金量为 0
        else:
            preResults.append(g[0])  # 若人数不少于第一座金矿所需人数，黄金量为 g[0]

    for i in range(0, n):  # 外层循环为金矿数量
        for j in range(0, w):  # 内层循环为工人数量
            if j < p[i]:
                results[j] = preResults[j]
            else:
                results[j] = max(preResults[j], preResults[j - p[i]] + g[i])
        preResults = results
    return results


# print(goldMining(5, 10, G, L))
if __name__ == '__main__':
    G = [400, 500, 200, 300, 350]
    L = [5, 5, 3, 4, 3]
    print(goldMine(5, 10, G, L))
    # print(goldMining(5, 10, G, L))
